package style.zcyLeetCode.a_0006_图;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Stack;

/**
 * 深度优先遍历
 * 1、利用栈实现
 * 2、从源节点开始把节点按照深度放入栈。然后弹出
 * 3、每弹出一个点，把该节点下一个没有进过栈的邻接点放入队列
 * 4、直到栈变空
 */
public class DFS {
    // 点
    public static class Node {
        public int value; // 数据项（点上的值）
        public int in;  // 入度
        public int out; // 出度
        public ArrayList<Node> nexts; // 当前点的直接邻居有哪些点
        public ArrayList<Edge> edges; // 当前点的直接连接的边（由当前点发散出去的边）

        public Node(int value) {
            this.value = value;
            in = 0;
            out = 0;
            nexts = new ArrayList<>();
            edges = new ArrayList<>();
        }
    }

    // 边
    public static class Edge {
        public int weight; // 边的权值
        public Node from;  // 表示有向边
        public Node to;    // 表示有向边

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }

    // 图
    public static class Graph {
        public HashMap<Integer, Node> nodes;  // 点集
        public HashSet<Edge> edges;           // 边集

        public Graph() {
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }
    }

    /**
     * 深度优先遍历
     * @param node
     */
    public static void dfs(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        HashSet<Node> set = new HashSet<>();
        stack.add(node);
        set.add(node);
        System.out.println(node.value);
        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            for (Node next : cur.nexts) {
                if (!set.contains(next)) {
                    stack.push(cur);  // 当前节点进栈
                    stack.push(next); // 下一个next节点进展
                    set.add(next);    // 下一个next入set
                    System.out.println(next.value);
                    break;
                }
            }
        }
    }
}
